#include<iostream>
using namespace std;



void print(int *arr,int n);


void swap(int *left, int *right)
{
    int temp = *left;
    *left = *right;
    *right = temp;
}




void shellSort(int *arr ,int len)
{
    int n = len/2;
    while( n>=1)
    {
         for(int i=0;i < n; i++)
         {
              for(int k=i+n;k<len;k=k+n)
              {
                  int j =k;
                  while(j>=n && arr[j] < arr[j-n])
                       swap(arr[j],arr[j-n]);
                       j-=n;
              };
         }
    }

}






void print(int *arr,int n)
{
    for(int i=0;i<n;i++)
        cout<< arr[i]<<' ' ;
    cout<< endl;

 }

int main()
{
    int a[11] ={2, 8, 4, 5, 9, 4, 42, 0, 3, 6, 8};
    int n=11;
    shellSort(a,n);
    print(a,n);
    return 0;
}


